package 双指针;

/**
 * @Author Weton Li
 * @Date 2021/3/3 21:46
 */
public class 五_二分法 {

    public static int binary_search(int[] nums, int x) {

        int n = nums.length;
        int startp = 0;
        int endp = n - 1;
        for (int i = 0; i < n / 2; i++) {

            int mid = (startp + endp) / 2;

            if (x < nums[mid]) {
                endp = mid - 1; // startp = 0不变
            } else if (x > nums[mid]) {
                startp = mid + 1; // endp = n-1不变
            } else {
                return mid;
            }
        }
        return -1;
    }

    public static int recursion_binary_search(int[] nums, int x, int fromIndex, int toIndex) {
        int n = nums.length;
        if (x < nums[fromIndex] || x > nums[toIndex] || fromIndex > toIndex) {
            return -1;
        }
        int mid = (fromIndex + toIndex) / 2;
        if (x < nums[mid]) {
            return recursion_binary_search(nums, x, 0, mid - 1);
        } else if (x > nums[mid]) {
            return recursion_binary_search(nums, x, mid + 1, n - 1);
        } else {
            return mid;
        }

    }

    public static void main(String[] args) {
        int[] input = {11, 22, 33, 99, 511, 666};
//        int result = binary_search(input, 666);
        int result = recursion_binary_search(input, 666, 0, input.length - 1);
        System.out.println("该数在" + (result + 1));
    }
}
